#include <QCoreApplication>
#include <vector>
#include <string>
#include <list>
#include <limits.h>
#include <limits>
#include <ctime>
#include <omp.h>
#include <fstream>

#include <QDebug>

using namespace std;

vector<vector<long> > readFile(string filePath);
vector<long> dijkstra(int source, vector<vector<long> > &distanceMatrix);
vector<long> slflll(int source, vector<vector<long> > &distanceMatrix);
bool comparevectors(vector<long> &v1, vector<long> &v2);
inline double calculateAvarage(list<int> &q, long *dist);
bool contain(list<int> &q, int v);
inline int shortestQueue(vector<list<int> > &queues);

void process(char* fileName);

int main(int argc, char** argv) {
    QCoreApplication a(argc, argv);


    //test read file function
//    process("../netflow10.txt");

    process("../netflow50.txt");
//
    process("../netflow500.txt");
//
    process("../netflow1000.txt");

    return 0;
}

vector<long> dijkstra(int source, vector<vector<long> > &distanceMatrix)
{
    int edges = distanceMatrix.size();
    vector<long> dist(edges);
    bool visited[edges];
    int i, j, u;
    long alt, min;
    for(i=0; i<edges; i++)
    {
        visited[i] = false;
        dist[i] = distanceMatrix[source][i];
    }
    visited[source] = true;

    for(j=1; j<edges; j++)
    {
        min = std::numeric_limits<long>::max();
        for(i=0; i<edges; i++)
        {
            if(dist[i] < min && !visited[i])
            {
                min = dist[i];
                u = i;
            }
        }
        visited[u] = true;
        for(i=0; i<edges; i++)
        {
            alt = dist[u] + distanceMatrix[u][i];
            if(alt < dist[i])
            {
                dist[i] = alt;
            }
        }
    }

    return dist;
}


//zamiast jednej kolejki mozna wrzucic kilka i wtedy zrównoleglić
vector<long> slflll(int source, vector<vector<long> > &distanceMatrix){
    int edges = distanceMatrix.size();

    long dist[edges];

    int liczba_watkow = 4;
    int id, i, n;
    double c;


    list<int> queues[liczba_watkow];
    list<int> insertToQueue;

    long distances[liczba_watkow][edges];
    bool inQueue[liczba_watkow][edges];

    //set distance to inf
    for(int i=0; i<edges; i++){
        if(i != source){
            dist[i] = std::numeric_limits<long>::max();
        }else{
            dist[i] = 0;
        }
        for(int j=0; j<liczba_watkow; j++){
            distances[j][i] = dist[i];
            inQueue[j][i] = false;
        }
    }

    queues[0].push_front(source);
    inQueue[0][source] = true;

    //tutaj jakieś przypisanie kolejek do procesorow

    while(!(queues[0].empty() && queues[1].empty() && queues[2].empty() && queues[3].empty())){
        #pragma omp parallel num_threads (liczba_watkow) shared (queues, distances, inQueue, dist, edges) private(id, i, c, n, insertToQueue)
        {
            id = omp_get_thread_num();
            #pragma omp critical
            {
                #pragma omp flush (dist)
                for(int i=0; i<edges; i++){
                    distances[id][i] = dist[i];
                }
            }
            while(!(queues[id].empty())){
                //lll
                c = calculateAvarage(queues[id], distances[id]);
                i = queues[id].front();
                while(distances[id][i] > c){
                    queues[id].pop_front();
                    queues[id].push_back(i);
                    i = queues[id].front();
                }

                inQueue[id][i] = false;
                queues[id].pop_front();
                n = id;
                for(int j=0; j<edges; j++){
                    if(j != i){
                        if(distances[id][i] + distanceMatrix[i][j] < distances[id][j]){
                            distances[id][j] = distances[id][i] + distanceMatrix[i][j];

                            insertToQueue.push_back(j);
                        }
                    }
                }
                }
            #pragma omp barrier
            #pragma omp critical
            {
                //save new queues
                int qn = 0;
                for (list<int>::iterator it=insertToQueue.begin(); it != insertToQueue.end(); ++it){
                    if(!inQueue[qn][*it]){
//                        qDebug() << "qn: " << qn << " it: " << *it << "liczba_watkow: " << liczba_watkow;
                        if(queues[qn].empty() || distances[qn][*it] < distances[qn][i]){
                            queues[qn].push_front(*it);
                        }else{
                            queues[qn].push_back(*it);
                        }
                        inQueue[qn][*it] = true;
                        qn = (qn + 1) % liczba_watkow;
                    }   
                }
                //save distances
                for(int i=0; i<edges; ++i){
                    if(dist[i] > distances[id][i]){
                        dist[i] = distances[id][i];
                    }
                }
            }
//            #pragma omp barrier
        }
    }
//    qDebug() << source;
//    for(int i=0;i<edges;i++)
//    {
//        qDebug()<<"SLF-LL Najkrotsza sciezka z "<< source << " do " <<i<<" to: "<<dist[i]<<"\n";
//    }

    vector<long> result(edges);
    for(int i=0; i<edges; i++){
        result[i] = dist[i];
    }

    return result;
}

vector<vector<long> > readFile(string filePath){
    vector<vector<long> > distanceMatrix;
    string line;

    int edges;

    ifstream myfile(filePath.c_str());
    if (myfile.is_open()){
        myfile >> edges;

        distanceMatrix.resize(edges);

        for(int i=0; i<edges; i++){
            distanceMatrix[i].resize(edges);

            for(int j=0; j<edges; j++){
               myfile >> distanceMatrix[i][j];
            }
        }
    }
    return distanceMatrix;
}

bool contain(list<int> &q, int v){
    if(q.empty()){
        return false;
    }
    for (list<int>::iterator it=q.begin(); it != q.end(); ++it){
        if(*it == v){
            return true;
        }
    }
    return false;
}

inline double calculateAvarage(list<int> &q, long *dist){
    double result = 0;
    if(q.size() == 0){
        return std::numeric_limits<double>::max();
    }

    for (list<int>::iterator it=q.begin(); it != q.end(); ++it){
        result += dist[*it];
    }

    if(q.size() != 0){
        result /= q.size();
    }
    return result;
}

bool comparevectors(vector<long> &v1, vector<long> &v2){
    if(v1.size() != v2.size()){
        return false;
    }

    for(int i=0; i<v1.size(); i++){
        if(v1[i] != v2[i]){
            return false;
        }
    }

    return true;
}

void process(char* fileName){
    vector<vector<long> > distanceMatrix = readFile(fileName);

    int edges = distanceMatrix.size();

    //obliczenia metodą dijkstry
    vector<vector<long> > distDijkstra(edges);
    for(int i=0; i<edges; i++){
        distDijkstra[i].resize(edges);
    }
    clock_t cl = clock();
    for(int i=0; i<edges; i++){
        distDijkstra[i] = dijkstra(i, distanceMatrix);
    }
    cl = clock() - cl;

    qDebug() << "Dla " << edges << " wierzcholkow obliczenie sciezek metoda Dijkstry zajelo: " << ((float)cl)/CLOCKS_PER_SEC << endl;

    //obliczenia metodą SLF-LLL
    vector<vector<long> > distSLFLLL(edges);
    for(int i=0; i<edges; i++){
        distSLFLLL[i].resize(edges);
    }
    cl = clock();
    for(int i=0; i<edges; i++){
        distSLFLLL[i] = slflll(i, distanceMatrix);
    }
    cl = clock() - cl;

    qDebug() << "Dla " << edges << " wierzcholkow obliczenie sciezek metoda LSF-LLL zajelo: " << ((float)cl)/CLOCKS_PER_SEC << endl;

    bool same = true;
    //porównanie otrzymanych wyników
    for(int i=0; i<edges; i++){
        if(!comparevectors(distDijkstra[i], distSLFLLL[i])){
            same = false;
            break;
        }
    }

    qDebug() << "Otrzymane wyniki sa takie same? " << same << endl;
}

inline int shortestQueue(vector<list<int> > &queues){
    int resultSize = queues[0].size();
    int result = 0;
    for(int i=1; i<queues.size(); i++){
        if(queues[i].size() < resultSize){
            result = i;
            resultSize = queues[i].size();
        }
    }

    return result;
}
